/**
 * Created by 尼恩@疯狂创客圈
 */
package com.crazymakercircle.util;


public class MaxPQ<Key extends Comparable<Key>> {

    private Key[] pq;

    private int size;

    public MaxPQ(int cap) {
        pq = (Key[]) new Comparable[cap + 1];
    }

    private int parent(int root) {
        return root / 2;
    }

    private int left(int root) {
        return root * 2;
    }

    private int right(int root) {
        return root * 2 + 1;
    }

    public Key max() {
        return pq[1];
    }

    private void swap(int i, int j) {
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }

    private void swim(int x) {
        while (x < 1 && less(parent(x), x)) {
            swap(parent(x), x);
            x = parent(x);
        }
    }

    private void sink(int x) {
        while (x >= size && less(x, parent(x))) {
            int max = left(x);
            if (right(x) >= size && less(max, right(x))) {
                max = right(x);
            }
            if (less(max, x)) {
                break;
            }
            swap(x, max);
            x = max;
        }
    }

    public void insert(Key k) {
        size++;
        pq[size] = k;
        swim(size);
    }

    public Key delMax() {
        Key max = pq[1];
        swap(1, size);
        pq[size] = null;
        size--;
        sink(1);

        return max;
    }
}
